package io.github.hadyang.leetcode.offer;

import org.junit.Test;

import java.util.HashMap;
import java.util.Map;

import io.github.hadyang.leetcode.TreeNode;

/** @author haoyang.shi */
public class ReConstructBinaryTree {

  @Test
  public void test() {
    TreeNode res =
        reConstructBinaryTree(new int[] {1, 2, 3, 4, 5, 6, 7}, new int[] {3, 2, 4, 1, 6, 5, 7});
    System.out.println(res);

    System.out.println();
  }

  public TreeNode reConstructBinaryTree(int[] pre, int[] in) {
    Map<Integer, Integer> preIndex = new HashMap<>();
    for (int i = 0; i < pre.length; i++) {
      preIndex.put(pre[i], i);
    }

    return buildTree(preIndex, in, 0, in.length - 1);
  }

  private TreeNode buildTree(Map<Integer, Integer> preIndex, int[] in, int start, int end) {
    if (start == end) {
      return new TreeNode(in[start]);
    }

    int indexOfRoot = start;
    for (int i = start; i <= end; i++) {
      if (preIndex.get(in[i]) < preIndex.get(in[indexOfRoot])) {
        indexOfRoot = i;
      }
    }

    TreeNode root = new TreeNode(in[indexOfRoot]);

    if (start <= indexOfRoot - 1) root.left = buildTree(preIndex, in, start, indexOfRoot - 1);

    if (indexOfRoot + 1 <= end) root.right = buildTree(preIndex, in, indexOfRoot + 1, end);

    return root;
  }
}
